package com.flower.algorithm.recursion;

/**
 * @ClassName Queens
 * @Description 八皇后问题
 * @Author 吃麻椒的花酱
 * @Date 2022/3/25 9:24
 * @Version 1.0
 */
/**
 * 思路分析：用一个一维数组表示八皇后棋盘，array的index表示当前处于第几个皇后(第几行)，值value表示处于第几列
 */
public class Queens {
    public static final int max=8;
    int[] array=new int[max];
    public  static int count=0;
   /**
    * @author 吃麻椒的花酱
    * @date 2022/3/25 9:34
    * @Description TODO
    * @param n:表示当前数组在棋盘中的位置（第几行） array[n] 表示第几列
    * @return boolean
    */
    public boolean judge(int n){
        for (int i = 0; i < n; i++) {
            // 等腰直角三角形原理判断是否在对角线
            if(array[i]==array[n]||Math.abs(array[i]-array[n])==Math.abs(i-n) )
            {
                return false;
            }
        }
        return true;
    }

    /**
     * @author 吃麻椒的花酱
     * @date 2022/3/25 9:49
     * @Description TODO
     * @param n 表示当前是第几个皇后
     * @return void
     */
    public void  checkCount(int n){
        if(n==max)
        {
            count++;
            return;
        }
        //依次放入八个皇后 并判断是否冲突
        for (int i = 0; i <max; i++) {
            //当前皇后处于第几列
            array[n]=i;
            if(judge(n))
            {
                checkCount(n+1);
            }
            // 在这里 i++发生回溯 judge(n) 不成立 则判断下一列
        }
    }

    public static void main(String[] args) {
        Queens queens = new Queens();
        queens.checkCount(0);
        System.out.println(count);
    }
}
